public class text19 {


    public static void guibing(int[]arr,int left,int mid,int right)
    {
        int i=left;
        int j=mid+1;
        int[]arr2=new int[right-left+1];
        int k=0;
        while(i<=mid&&j<=right)
        {
            if(arr[i]<=arr[j])
            {
                arr2[k++]=arr[i];
                i++;

            }
            else
            {
                arr2[k++]=arr[j];
                j++;

            }
        }
        while(i<=mid)
        {
            arr2[k++]=arr[i];
            i++;
        }
        while(j<=right)
        {
            arr2[k++]=arr[j];
            j++;
        }
        for(i=0;i<k;i++)
        {
            arr[i+left]=arr2[i];
        }


    }
    public static void paixu(int[]arr,int left,int right)
    {
        if(left>=right)
        {
            return;
        }
        int mid=(left+right)/2;
        paixu(arr,left,mid);
        paixu(arr,mid+1,right);
        guibing(arr,left,mid,right);
    }



    public static void main(String[] args) {
        int[]arr={5,3,9,1,2};
        paixu(arr,0,arr.length-1);
        System.out.println(arr);

    }
}
